package lanQiaoBei.数学知识.组合数学;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/*
 https://blog.csdn.net/Jacob0824/article/details/122757250 卢卡斯定理
 */
public class P3 {
       static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       static int n,p;
       
       static int qmi(int a,int k){
    	      int res=1;
    	      while(k>0){
    	    	  if((k&1)==1)res=res*a%p;
    	    	  k>>=1;
    	    	  a=a*a%p;
    	      }
    	      return res;
       }
       static int C(int a,int b){
    	     int res=1;
    	     for(int i=a,j=1;i>a-b;i--,j++){
    	    	 res=(int)(1L*res*i%p);
    	    	 res=(int)(1L*res*qmi(j,p-2)%p);
    	     }
    	     return res;
       }
       static int lucas(long a,long b){
    	      if(a<p&&b<p)return C((int)a,(int)b);
    	      return C((int)(a%p),(int)(b%p))*lucas(a/p, b/p)%p;
       }
       public static void main(String[] args) throws  IOException {
		      n=Integer.parseInt(br.readLine());
		      while(n-->0){
		    	  String[]ss=br.readLine().split(" ");
		    	  long a=Integer.parseInt(ss[0]),b=Integer.parseInt(ss[1]);p=Integer.parseInt(ss[2]);
		    	  System.out.println(lucas(a,b));
		      }
	}
}
